package main.java.indi.zyj.coderecord;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class C {
    static List<List<Integer>> res = new ArrayList<>();
    static LinkedList<Integer> temp = new LinkedList<>();
    static int repeat_num = 0;
    public static void main(String[] args) {
        int[] candidates = {8,7,4,3};
        int target = 11;
        repeat_num = 5 ;
//        Arrays.sort(candidates);

        combinationSum(0,candidates,target);


    }
    public static List<List<Integer>> combinationSum(int pos,int[] candidates, int target) {
        bfs(0,candidates,target,0);
        return res;
    }
    //pos代表层数
    public static void bfs(int pos, int[] candidates, int target, int sum){

        if(sum == target){
            res.add(new ArrayList<>(temp));
            return;
        }

        if(sum > target) return;

        //i代表选择的数量
        for(int i = pos ; i < candidates.length;i++){
            temp.add(candidates[i]);
            sum = sum + candidates[i];
            bfs(i,candidates,target,sum);
            sum = sum - candidates[i];
            temp.removeLast();
        }
    }
}
